////////////////////////////////////////////////////////////////////
//   
//   File: connect4_chapel.chpl 
//   Team: Patrick Copeland, Deanna Fink, Jordan Hildebrandt
//   Date: 8 February 2012
//   Time: 23:20
//   Desc: An implementation of Connect4 in Chapel
//
////////////////////////////////////////////////////////////////////


use Random, Time, minimax;

const NUM_COLS : int = 7;   
const NUM_ROWS : int = 6;


proc playGame(state, initialCurrPlayerSymbol, playerXDef, playerODef){
   var gameOver : bool = false;
   var currPlayerSymbol = initialCurrPlayerSymbol;
   
   var terminalResults : string;      //variable pre-definition
   var copiedState : [0..NUM_COLS-1][0..NUM_ROWS-1] string;
   var playerMove : int;   
   
   while(!gameOver){
      printState(state);
      
      // Copy the state, so the playerDef getMove function can change it if it wants
      //copiedState[0..NUM_COLS][0..NUM_ROWS] = state[0..NUM_COLS][0..NUM_ROWS];
      copiedState = stateCopy(state);
      if(currPlayerSymbol == 'x'){
         playerMove = playerXDef.getMove(copiedState);
      } else {
         playerMove = playerODef.getMove(copiedState);
      }
      
      writeln("=========================================");
   
      //Check if game is over...
      if (!isValidMove(state, playerMove)){
         writeln("**************\nInvalid move\n**************\n");
         terminalResults = otherPlayer(currPlayerSymbol);
         gameOver = true;
      } else {
         // Make the move actually occur
          move(state, playerMove, currPlayerSymbol);
         
         // Check if game is over
         terminalResults = isTerminalState(state);
         if(terminalResults == "x" || terminalResults == "o" || terminalResults == "c"){
            gameOver = true;
         }
         // Switch whose turn it is
         currPlayerSymbol = otherPlayer(currPlayerSymbol);
      }
   }
   showResults(state, terminalResults);
}

//switch players
proc otherPlayer(player){
   if (player == 'x'){
      return 'o';
   } else {
      return 'x';
   }
}

proc showResults(state, result){
   writeln();
   printState(state);
   if (result == 'c'){
      writeln("\n****************\nCat game. Nobody wins.\n****************\n");
   } else {
      writeln("\n****************\nThe winner is: ", result, "\n****************\n");
   }
}

//Make an empty state
proc makeInitState(){
   var gameBoard : [0..NUM_COLS-1][0..NUM_ROWS-1] string;
      forall i in [0..NUM_COLS-1]{
         forall j in [0..NUM_ROWS-1]{
         gameBoard[i][j] = "_";
      }
   }
   return gameBoard;
}

//Get the list corresponding to a column with the given colID
proc getColumn(state, colID){
   return state[colID][0..NUM_ROWS-1];
}

// Get the piece at the current position (might be 'x', 'o', or '_')
proc getPiece(state, colID, rowID){
   return getColumn(state, colID)[rowID];
}

//Neatly print out the board state
proc printState(state){
   // print column headings
   for i in [0..NUM_COLS-1]{
      write(i + " ");
   }
      writeln();
   
      for rowID in [0..NUM_ROWS-1]{
            for colID in [0..NUM_COLS-1] {
               write(getPiece(state, colID, rowID) + " ");
      }
            writeln();
   }
}

//Copy the state so it may be changed without messing up the original
proc stateCopy(state){
   var newState : [0..NUM_COLS-1][0..NUM_ROWS-1] string;
   newState[0..NUM_COLS-1][0..NUM_ROWS-1] = state[0..NUM_COLS-1][0..NUM_ROWS-1];
   return newState;
}

//Changes (mutates) state to reflect the given move (indicated by colID, done by player
//'x' or 'o').  If the requested column is full, the request is ignored.
proc move(state, colID, player){
   if(!isFullCol(state, colID)){
            var boardCol = getColumn(state, colID);
            var rowID : int = getLowestRowInCol(boardCol);
            state[colID][rowID] = player;
   }
}

//Returns row in which a move may be made for this column, or false if the column is full
proc getLowestRowInCol(boardCol){
   //Start at top row (rowID == 0), and go down until you find a piece
   var piece : string;
   var rowID : int;
   var finalRowID : int;
   
   for rowID in [0..NUM_ROWS-1] {
      finalRowID = rowID;
            piece = boardCol[rowID];
            if(piece == 'x' || piece == 'o'){
               if(rowID == 0){
                     return false;    //column full
               } else {
                     return rowID-1;    //Just above current row is open
         }
      }
      //else still looking for top piece
   }
   
   //writeln("\nLOWEST ROW IN COL: ", finalRowID);
   return finalRowID;    //No pieces in this column at all, so return NUM_ROWS-1
}       

//Returns true if the move is valid (correct input type and not a full column).
proc isValidMove(state, colID){
   //if(type(colID) != type(1) || colID < 0 || colID > NUM_COLS - 1){
      if(colID < 0 || colID > NUM_COLS - 1){
            return false;
      } else {
            return !isFullCol(state, colID);
   }
}

//Returns true if the given column is full in the given state, false otherwise.
proc isFullCol(state, colID){
    return getColumn(state, colID)[0] != '_';
}

//////////////////////////////////////////////////////////////////

//Returns 'x' if x won, 'o' if o won, False if no one has won, and 'c' for a tie
proc isTerminalState(state){
   var blankSpace = false;
   var seq = 1;
   var basePiece : string;
   
   // Test horizontal
   for colID in [0..NUM_COLS-4]{
      for rowID in [0..NUM_ROWS-1]{
         basePiece = getPiece(state, colID, rowID);
         if basePiece != "_"{
            while basePiece == getPiece(state, colID + seq, rowID) {
               seq = seq + 1;
               if seq == 4 {
                  return basePiece;
               }
            }
            
            // restart sequence
            seq = 1;
            
         } else {
            blankSpace = true;
         }
      }
   }
   
   seq = 1;
   
   // Test vertical
   for rowID in [0..NUM_ROWS-4]{
      for colID in [0..NUM_COLS-1]{
         basePiece = getPiece(state, colID, rowID);
         if basePiece != "_"{
            while basePiece == getPiece(state, colID, rowID + seq) {
               seq = seq + 1;
               if seq == 4 {
                  return basePiece;
               }
            }
            
            // restart sequence
            seq = 1;
            
         } else {
            blankSpace = true;
         }
      }
   }
   
   seq = 1;
   
   // Test up and right
   for colID in [0..NUM_COLS-4]{
      for rowID in [4..NUM_ROWS-1] by -1 {
         basePiece = getPiece(state, colID, rowID);
         if basePiece != "_"{
            while basePiece == getPiece(state, colID + seq, rowID - seq) {
               seq = seq + 1;
               if seq == 4 {
                  return basePiece;
               }
            }
            
            // restart sequence
            seq = 1;
         } else {
            blankSpace = true;
         }
      }
   }
   
   seq = 1;
   
   // Test down and right
   for colID in [0..NUM_COLS-4]{
      for rowID in [0..NUM_ROWS-4]{
         basePiece = getPiece(state, colID, rowID);
         if basePiece != "_"{
            while basePiece == getPiece(state, colID + seq, rowID + seq) {
               seq = seq + 1;
               if seq == 4 {
                  return basePiece;
               }
            }
            
            // restart sequence
            seq = 1;
            
         } else {
            blankSpace = true;
         }
      }
   }
   
   if (blankSpace) {
      return "*";      // game is not over
   } else {
      return "c";      // cat game
   }
}

//Does an "or" on a list of booleans, except that when it finds anything non-False, it
//returns it, instead of returning True.
proc orList(boolList){
   for b in boolList do{
      if (b){
         return b;
      }
   }
   return false;
}






proc isNSeqHoriz(n, state, col, row, symbol) {
   for i in [0..n-1] {
      if state[i][row] != symbol {
         return false;
      }
   }
   
   return true;
}

proc isNSeqVert(n, state, col, row, symbol) {
   for i in [0..n-1] {
      if state[col][i] != symbol {
         return false;
      }
   }
   
   return true;
}

proc isNSeqUpDiag(n, state, col, row, symbol) {
   for i in [0..n-1] {
      if state[col+i][row-i] != symbol {
         return false;
      }
   }
   
   return true;
}

proc isNSeqDownDiag(n, state, col, row, symbol) {
   for i in [0..n-1] {
      if state[col+i][row+i] != symbol {
         return false;
      }
   }
   
   return true;
}










////////////////////////////////////////////////////////////////////////////////
// Player definitions

//Any player definition should inherit from this class, and define the
//getMove method.

//HumanDef asks for the move to be input from the keyboard
class HumanDef {
   proc HumanDef(playerSymbol){
      var playerSymbol : string;
      playerSymbol = playerSymbol;
      //super(HumanDef).GeneralTestDef(playerSymbol);
   }
   proc getMove(state){
      var move : int;
      write("Enter move: ");
      return read(int);
   }

   proc invalidMoveResponse(){
      writeln("Invalid move, human.  Try again. ");
   }
}


//RandomDef randomly (stupidly) selects a move until a valid one is found
class RandomDef{

   
   proc RandomDef(playerSymbol){
      var playerSymbol : string;
      playerSymbol = playerSymbol;
   }

   proc getMove(state){
           var move = randomInt();
           
           while (!isValidMove(state, move)) {
              move = randomInt();
           }
           
           return randomInt();    //get random move - will keep trying until valid
   }
    
   proc invalidMoveResponse(){
          return;   // No response to invalid move - just try again
   }

   proc randomInt() {
      var array : [0..0] real;
      fillRandom(array);
   
      var temp = array[0] * 100;
      var randomInt: int = temp:int;
      
      return randomInt % NUM_COLS;
   }
}


//Then to run a game all should need is this (?)
proc main() {
   playGame(makeInitState(), 'x', new RandomDef('x'), new MiniMaxPlayer('o'));
}



















/////////////////////////////////////////////////////////////////////////

// Debugging functions

//Make a state, given a history of moves.
//X always moves first.  History is a list of columns in which moves were made.
proc makeState(history){
   var players = ['x', 'o'];
   var state = makeInitState();
   var playerID : int = 0;
   for aMove in history {
      move(state, aMove, players(playerID));
      playerID = (playerID + 1) % 2;
   }
   return state;
}

// proc testGetNSeqTests(){
//    state = makeInitState();
//    var result: string;
//    for rowID in 0..NUM_ROWS-1{
//       for colID in 0..NUM_COLS-1{
//          tests = getNSeqTests(4, state, colID, rowID);
//          result = "";
//          for t in tests{
//             if (t == isNSeqHoriz){
//                result += 'h';
//             } else if (t == isNSeqVert){
//                result += 'v';
//             } else if (t == isNSeqUpRight){
//                result += 'u';
//             } else if (t == isNSeqDownRight){
//                result += 'd';
//             }
//          }
//          for i in 0..4-len(tests){
//             result += '_';
//          }
//          writeln(result + " ");
//          
//       }
//       writeln();
//    }
// }
// 
//
// proc testIsGeneralNSeq(){
//    //vertNSeq at col 6, row 2
//    //horizNSeq at col 3, row 5
//    //upRightNSeq at col 3, row 5
//    //downRightNSeq at col 3, row 2
//                 // top -> bottom
//     testState = [['_', '_', '_', '_', '_', '_'], // col 0
//                  ['_', '_', '_', '_', '_', '_'],
//                  ['_', '_', '_', '_', '_', '_'], 
//                  ['_', '_', 'x', 'o', 'o', 'x'], 
//                  ['_', '_', '_', 'x', 'x', 'x'],
//                  ['_', '_', '_', 'x', 'x', 'x'],
//                  ['_', '_', 'x', 'x', 'x', 'x']]; // col 7
//    printState(testState);
//    writeln(isNSeqVert(4, testState, 6, 2));
//    writeln(isNSeqHoriz(4, testState, 3, 5));
//    writeln(isNSeqDownRight(4, testState, 3, 2));
//    writeln(isNSeqUpRight(4, testState, 3, 5));
// }
// 
// proc testCatGame(){
//     testState = [['x', 'x', 'x', 'o', 'o', 'o'], // col 0
//                  ['o', 'o', 'o', 'x', 'x', 'x'],
//                  ['x', 'x', 'x', 'o', 'o', 'o'], 
//                  ['o', 'o', 'o', 'x', 'x', 'x'],
//                  ['x', 'x', 'x', 'o', 'o', 'o'], 
//                  ['o', 'o', 'o', 'x', 'x', 'x'],
//                  ['x', 'x', 'x', 'o', 'o', 'o']]; // col 7
//    writeln(isTerminalState(testState));
// }